終於到了最後一天了，讓我們來複習一下到底學的了什麼東西吧．

動態規劃

一個動態規劃問題，可以分成三個重點
1.重疊子問題

2.找到狀態轉移方程

3.優化成最佳子結構

要解動態規劃問題，不用一開始就想要直接寫出來．先試著寫寫看暴力解法，就算效能很差也沒關係．

要寫出暴力解法，就要暸解上一個狀態怎麼變成現在的狀態的．仔細觀察題意的需求，來列出狀態轉移方程式，這段是整個題目最困難的．

例如昨天的最長迴文字串，可以藉由前一個狀態，再分別拼接上頭尾，獲得新的狀態．

有了暴力解法後，可以藉由觀察哪些部分重複出現，便是重疊子問題，可以藉由一些技巧來減少重疊子問題，進而優化效能

在撰寫這個部分時，要注意最佳子結構的問題，所謂的最佳子結構就是子問題之間不會互相干擾，如果你發現你的解法順序會造成子問題答案不固定，那就有可能子問題沒有最佳子結構

例如我們提過的memo，將我們算過答案的子問題記錄下來，到需要計算子問題前，先去memo裡面看一看有沒有算過，如果有了就可以省下這份功．

另外一個常用的方法就是 DP Table，暴力解法通常都是從結果一路遞迴回到起始狀態，然後得出結果，而使用DP Table，由起始狀態一路往外延伸，最終填滿Table．然後從DP Table中找到答案的那個元素，回傳回去．

除了這些優化時間複雜度的技巧以外，還有稱之為狀態壓縮的優化空間複雜度的技巧．

例如費波那契數列，他的新數值，只跟前面兩個數值有關係．

F0=0，F1=1，Fn=Fn-1+Fn-2（n>=2，n∈N*）

因此我們可以只記錄下需要的部分，其餘部分可以捨棄．看清題意，選擇要留下的部分．

我們再來複習一次，動態規劃問題解答的範式

1.確定初始狀態

2.確定狀態

3.確定選擇

4.明確狀態變化的dp函數

有了一個範式後，我們就使用這個範式作為最高指導原則，研究了一些動態規劃的演算法．

回溯演算法

其本質是遍歷一顆決策樹，在樹的節點之間移動時，做出選擇或是撤銷選擇．直到決策樹的底層無法再做更多事情了

BFS演算法

廣度優先搜尋(Breadth-First Search, BFS)是一種”將一些問題抽象成圖，從圖的某一個點開始，往四周擴散”的演算法，像是沾到墨水的布，向四方擴散．其特點是定是最短的路徑，相對來說，所需要的空間複雜度會比深度優先搜尋(Depth-First Search,DFS)大上很多．

雙指標

比起只用一個指標，使用雙指標可以做到一些特殊的事情

1.快慢指標：有一組一快一慢的指標，主要是用來解決LinkedList的問題，例如典型的判斷一個LinkedList是否有環

2.左右指標:有一組分成左右的指標，主要是用來解決陣列或是字串的問題，例如二分搜尋

二分演算法

就是從中間切開，進行運算，但是其很多的小細節需要注意，例如要使用≤或是< ，左右的部分要加或減等等，由於不好追蹤又容易錯，撰寫時需要更加注意

滑動視窗演算法

我們維護一個不停移動的視窗，然後更新答案，先找到一個正確答案，然後不停地縮小視窗的大小，直到不符合題目所需要的答案為止．那前一步就是題目所需要的極值答案

最後我們使用了這些技巧，來研究了一些經典的動態規劃題目

例如：最長遞增子序列，俄羅斯套娃信封問題，最長公用次序列，字串最小編輯距離等等的問題…

哇看來我們這30天真的獲得不少收穫呢，不過演算法還有許多難題跟樂趣等著我們去發掘呢．現在的情況就像是剛買完裝備，出新手村一樣．接下來就是各位的大冒險了．希望我提供的這些武器可以幫助大家在面對難題時不至於手忙腳亂！

那我們有緣再見拉！感謝各位！